package com.jusntow;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author justnow
 * Created on 2020-09-14
 * Description
 * 使用LidList来实现！
 */
public class Solution8_1 {

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(10);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
    }
}

class LruCache {
    // key -> ListNode(key, val)
    private HashMap<Integer, ListNode> map;
    // ListNode(k1, v1) <-> ListNode(k2, v2)...
    private LinkedList<ListNode> cache;
    // 最大容量
    private int cap;

    public LruCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
        this.cache = new LinkedList<>();
    }

    public int get(int key) {
        //1 判断链表中是否存在该节点
        if (!map.containsKey(key)) {
            return -1;
        }

        //2 获取节点的内容，同时把节点重新插入一次。
        int val = map.get(key).val;
        put(key, val);
        return val;
    }


    // 插入
    public void put(int key, int val) {
        //1 创建该节点
        ListNode node = new ListNode(key, val);

        //2 该节点已经存在，那么需要把它删除了，然后放到队首的位置
        if (map.containsKey(key)) {
            cache.remove(node);
            cache.addFirst(node);
        } else {
        //3 该节点不存在
            if (cap == cache.size()) {
                //4 队满了，移除最后一个节点
                ListNode removeNode = cache.removeLast();
                map.remove(removeNode.key);
            }
            //5 队没有满，直接添加到头部
            cache.addFirst(node);
            map.put(key, node);
        }
    }
}

class ListNode {
    int key;
    int val;
    public ListNode(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
